package com.jeff.learn.linkedlist;

import java.util.function.Consumer;

/**
 * 带哨兵节点的双向链表
 *
 * @author yaojianfeng
 */
public class DoublySentinelLinkedList {
    /**
     * 头哨兵节点
     */
    private Node headSentinelNode = new Node(null, Integer.MIN_VALUE, null);
    ;
    /**
     * 尾哨兵节点
     */
    private Node tailSentinelNode = new Node(null, Integer.MAX_VALUE, null);

    public DoublySentinelLinkedList() {
        headSentinelNode.setNext(tailSentinelNode);
        tailSentinelNode.setPrev(headSentinelNode);
    }

    /**
     * 根据索引获取节点
     *
     * @param inde 索引
     * @return 节点
     */
    public Node findNode(int index) {
        // 先判断索引是否越界
        if (index < 0) {
            throw new IndexOutOfBoundsException("索引不能为负数");
        }

        // 找到索引对应的节点 从头哨兵的next开始查找
        // 索引从0开始
        int currentIndex = 0;

        Node currentNode = headSentinelNode.getNext();
        //当前节点是尾哨兵节点,说明索引越界 退出循环 最大索引为currentIndex-1
        while (currentNode != tailSentinelNode) {
            if (currentIndex == index) {
                return currentNode;
            }
            currentIndex++;
            currentNode = currentNode.getNext();
        }
        // 索引越界
        throw new IndexOutOfBoundsException("索引越界: " + "最大索引为:" + (currentIndex - 1));
    }


    /**
     * 添加节点到头部
     * 只用关心头节点的后继节点与新节点的关系即可
     *
     * @param value
     * @return
     */
    public Node addHead(int value) {
        // 创建新的头节点
        Node newHead = new Node(null, value, null);
        return addHead(newHead);
    }

    /**
     * 添加目标节点到头部
     *
     * @param newHead 新头部节点
     * @return
     */
    public Node addHead(Node newHead) {
        // 获取原来的头节点
        Node oldHead = headSentinelNode.getNext();
        // 创建新的头节点 新节点的前驱节点为头哨兵节点
        newHead.setPrev(headSentinelNode);
        newHead.setNext(oldHead);

        // 设置新节点的前后关系
        headSentinelNode.setNext(newHead);
        oldHead.setPrev(newHead);
        return newHead;
    }

    /**
     * 添加节点到尾部
     * 只用关心尾节点的前驱节点与新节点的关系即可
     *
     * @param value
     * @return
     */
    public Node addTail(int value) {
        // 获取尾哨兵节点的原本前一个节点
        Node oldTail = tailSentinelNode.getPrev();
        // 创建新的尾节点
        Node newTail = new Node(oldTail, value, tailSentinelNode);
        // 设置新节点的前后关系
        tailSentinelNode.setPrev(newTail);
        oldTail.setNext(newTail);
        // 返回新节
        return newTail;
    }

    /**
     * 遍历节点,并执行consumer
     * 遍历的顺序为从头哨兵的next节点开始到尾哨兵的前一个节点结束
     *
     * @param consumer
     */
    public void forEach(Consumer<Node> consumer) {
        // 遍历的起点
        Node currentNode = headSentinelNode.getNext();
        //遍历节点,遍历到了尾哨兵节点,此时遍历结束,退出循环
        while (currentNode != tailSentinelNode) {
            consumer.accept(currentNode);
            currentNode = currentNode.getNext();
        }
    }

    /**
     * 插入指定位置的节点
     *
     * @param prevNode
     * @param index
     * @return
     */
    public Node insertNode(Node targetNode, int index) {

        return null;
    }


    /**
     * 删除指定位置的节点
     *
     * @param index 索引
     * @return 删除的节点
     */
    public Node removeNode(int index) {
        // 先判断索引是否越界
        if (index < 0) {
            throw new IndexOutOfBoundsException("索引不能为负数");
        }
        //找到索引对应的节点 不用考虑是否是头尾哨兵节点
        Node currentNode = findNode(index);
        Node prev = currentNode.getPrev();
        Node next = currentNode.getNext();
        // 节点的前驱节点的next指针指向当前节点的后继节点
        prev.setNext(next);
        // 节点的后继节点的prev指针指向当前节点的前驱节点
        next.setPrev(prev);

        // 找到节点后,删除节点
        return currentNode;
    }

    /**
     * 删除头节点
     *
     * @return 删除的节点
     */
    public Node removeHead() {
        return removeNode(0);
    }

    /**
     * 删除尾节点
     *
     * @return 删除的节点
     */
    public Node removeTail() {
        Node deleteNode = tailSentinelNode.getPrev();
        Node prev = deleteNode.getPrev();
        prev.setNext(tailSentinelNode);
        tailSentinelNode.setPrev(prev);
        return deleteNode;
    }

}
